import java.util.PriorityQueue;

//力扣23. 合并 K 个升序链表
//方法1:暴力算法
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode(-1);
        ListNode temp = ans;
        for(int i=0;i<lists.length;i++){
            ListNode curr = lists[i];
            temp.next = merge(temp.next,curr);
        }
        return ans.next;
    }
    public ListNode merge(ListNode ans,ListNode curr){
        ListNode temp = new ListNode(-1);
        ListNode res = temp , head1 = ans , head2 = curr;
        while(head1!=null&&head2!=null){
            if(head1.val>=head2.val){
                res.next = head2;
                head2 = head2.next;
            }else{
                res.next = head1;
                head1 = head1.next;
            }
            res = res.next;
        }
        while(head1!=null){
            res.next = head1;
            head1 = head1.next;
            res = res.next;
        }
        while(head2!=null){
            res.next = head2;
            head2 = head2.next;
            res = res.next;
        }
        return temp.next;
    }
}



//方法2:归并排序
class Solution1 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return mergeLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeLists(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeLists(lists, left, mid);
        ListNode l2 = mergeLists(lists, mid + 1, right);
        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}




//方法3:优先级队列
class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        return dummy.next;
    }
}